package oj;

//链表分割：现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
public class Solution_CM11 {
    public static ListNode partition(ListNode pHead,int x){
        //准备逻辑上的两个链表，分别用来保存小于x和大于x的结点
        //ans1保存小于x的结点
        ListNode ans1 = new ListNode(0);
        ListNode last1 = ans1;//ans1的尾结点
        //ans2保存大于x的结点
        ListNode ans2 = new ListNode(0);
        ListNode last2 = ans2;//ans2的尾结点
        //遍历整个链表
        ListNode cur = pHead;
        while (cur != null){
            ListNode next = cur.next;
            if(cur.val < x){
                cur.next = null;
                last1.next = cur;
                last1 = cur;
            }else{
                cur.next = null;
                last2.next = cur;
                last2 = cur;
            }
            //一个结点判断结束后，继续判断下一个结点
            cur = next;
        }
        //将这两个链表组合到一起
        last1.next = ans2.next;//跳过ans2，因为ans2只是一个工具结点
        return ans1.next;//跳过ans1，因为ans1也是工具结点
    }

    public static void main(String[] args) {

    }
}
